public class SortArray {

    public int[] sortArray(int[] nums) {
        int heapSize = nums.length;
        for (int i = nums.length / 2 - 1; i >= 0 ; i--) {
            heapify(nums, i, nums.length);
        }
        swap(nums, 0, --heapSize);
        while (heapSize > 0) {
            heapify(nums, 0, heapSize);
            swap(nums, 0, --heapSize);
        }
        return nums;
    }
    
    public void heapify(int[] nums, int i, int heapSize) {
        int left = 2 * i + 1;
        while (left < heapSize) {
            int largest = left + 1 < heapSize && nums[left + 1] > nums[left] ? left + 1 : left;
            largest = nums[largest] > nums[i] ? largest : i;
            if (largest == i) break;
            swap(nums, largest, i);
            i = largest;
            left = 2 * i + 1;
        }
    }
    
    public void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}
